
template <class Comparable>
PriorityHeap< Comparable >::PriorityHeap(uint32 capacity) : heapArray_(capacity+1), size_(0)
{

}

template <class Comparable>
void PriorityHeap< Comparable >::insert(const Comparable& comparable)
{
	if(size_ == heapArray_.size()-1)
	{
		heapArray_.push_back(Comparable());
	}

	//Bubble up
	uint32 hole = ++size_;
	for( ; hole > 1 && comparable < heapArray_[ hole / 2 ]; hole /= 2 )
		heapArray_[ hole ] = heapArray_[ hole / 2 ];
	heapArray_[ hole ] = comparable;
}

template <class Comparable>
const Comparable& PriorityHeap< Comparable >::findMin() const
{
	return heapArray_[1];
}

template <class Comparable>
void PriorityHeap< Comparable >::deleteMin()
{
	assert(!isEmpty() && "Error while attempting to delete element from empty heap.");
	heapArray_[1] = heapArray_[size_--];
	bubbleDown(1);

}

template <class Comparable>
bool PriorityHeap< Comparable >::isEmpty() const
{
	return size_ == 0;
}

template <class Comparable>
void PriorityHeap< Comparable >::clear()
{
	size_ = 0;
}

template <class Comparable>
void PriorityHeap< Comparable >::bubbleDown(uint32 hole)
{
	int child;
	Comparable tmp = heapArray_[hole];

	for( ; hole * 2 <= size_; hole = child )
	{
		child = hole * 2;
		if( child != size_ && heapArray_[child + 1] < heapArray_[child])
			child++;
		if( heapArray_[child] < tmp )
			heapArray_[hole] = heapArray_[child];
		else
			break;
	}
	heapArray_[ hole ] = tmp;
}